package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class CombinationSum {
//this backtracking is typical, remember it
  public ArrayList<ArrayList<Integer>> combinationSum1(int[] candidates,
      int target) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    int[] index = new int[20];
    index[0] = 0;
    Arrays.sort(candidates);
    comb(candidates, target, 0, index, 0, result);
    return result;
  }

  public void comb(int[] candidates, int target, int sum, int[] index,
      int level, ArrayList<ArrayList<Integer>> result) {
    if (sum > target)
      return;
    if (sum == target) {
      System.out.println("condition matched, the level is " + level + " and backtrack is " + Arrays.toString(index));
      ArrayList<Integer> arr = new ArrayList<Integer>();
      for (int i = 1; i <= level; i++) {
        arr.add(candidates[index[i]]);
      }
      result.add(arr);
    }
    //this is slightly different from other dfs, because we can use one element again and again
    for (int i = index[level]; i < candidates.length; i++) {
      index[level + 1] = i;
      System.out.println("the level is " + level + " and i is " + i + " and sum is " + sum + " and backtrack is " + Arrays.toString(index));
      comb(candidates, target, sum + candidates[i], index, level + 1, result);
    }
  }
  
  
  
  // pass both ETL
  public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates,
      int target) {
    // Start typing your Java solution below
    // DO NOT write main() function
    Arrays.sort(candidates);
    ArrayList<Integer> backtrack = new ArrayList<Integer>();
    backtrack.add(0);
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    cs(result, candidates, target, backtrack, 0, 0);
    return result;
  }

  public void cs(ArrayList<ArrayList<Integer>> result, int[] candidates,
      int target, ArrayList<Integer> backtrack, int pos, int sum) {
    if (target == sum) {
      // add everything in backtrack to result
      ArrayList<Integer> x = new ArrayList<Integer>();
      for (int i = 1; i <= pos; i++) {
        x.add(candidates[backtrack.get(i)]);
      }
      result.add(x);
      return;
    } else if (target < sum) {
      return;
    } else {
      for (int i = backtrack.get(pos); i < candidates.length; i++) {
        if (backtrack.size() > pos + 1) {
          backtrack.set(pos + 1, i);
        } else {
          backtrack.add(i);
        }
        cs(result, candidates, target, backtrack, pos + 1, sum + candidates[i]);
      }

    }
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] can = new int[] { 8, 7, 4, 3, 1 };
    int target = 11;
    CombinationSum c = new CombinationSum();
    System.out.println(c.combinationSum1(can, target).toString());

  }

}
